#include<iostream>
#include<queue>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;

//LCR.114.火星词典
string alienOrder(vector<string>& words){
    // 建立一个边哈希表，key值表示字符，val值表示哈希表用来存放该字符指向的所有字符
    // 因为查找该字符的指向字符时，可能会重复出现，所以内层哈希表用set型去重
    // 例：key=t;val=[d,c,a];表示t->d&&t->c&&t->a;
    unordered_map<char, unordered_set<char>> edges;
    //建立一个入度哈希表，用来存放每个字符的入度
    //key值表示字符，val值表示该字符对应的入度
    unordered_map<char, int> in;

    //先遍历整个词典，将所有出现的字符存放到入度哈希表中并将入度初始化为0，防止后面某些字符没有遍历到
    for(auto s : words){
        for(auto ch : s){
            if(in.count(ch)==0){
                in[ch] = 0;
            }
        }
    }

    //两层for循环遍历词典，建AOV图
    for (int i = 0; i < words.size(); i++){
        string s1 = words[i];
        for (int j = i + 1; j < words.size(); j++){
            string s2 = words[j];

            //两个指针，一个指向第一个字符串中的起始位置，一个指向第二个字符串的起始位置
            int cur1 = 0, cur2 = 0;
            while(cur1<s1.size()&&cur2<s2.size()){
                //如果两个指针指向对应字符串中的字符不相同，表示s1[cur1]->s2[cur2]
                //s1的字符指向s2的字符，s2的字符入度+1
                if(s1[cur1]!=s2[cur2]){
                    //这里有一个细节，如果b->a重复出现，a字符的入度就会重复+1
                    //所以要进行一个判断，如果b字符的哈希表中已经存在字符a，直接跳过
                    if(edges[s1[cur1]].count(s2[cur2])==0){
                        edges[s1[cur1]].insert(s2[cur2]);
                        in[s2[cur2]]++;
                    }
                    //找到第一对不相同的字符就结束
                    break;
                }
                else{
                    cur1++;
                    cur2++;
                }
            }
            // 如果两个字符串没有找到相同的字符，有两种情况
            // 1.s1=ab;s2=abc;不用处理
            // 2.s1=abc;s2=ab;直接返回空串，因为违反规则
            if(cur2==s2.size()&&cur1<s1.size()){
                return "";
            }
        }
    }

    //设置一个结果字符串用来存放字符的顺序
    string ret;
    //设置一个队列
    queue<char> q;
    //遍历入度哈希表将所有入度为0的字符入队
    for(auto& [ch,count] : in){
        if(count==0){
            q.push(ch);
        }
    }

    //bfs实现拓扑排序
    while(!q.empty()){
        //获取队头字符并出队
        char ch = q.front();
        q.pop();

        //结果字符串加上队头字符
        ret += ch;

        //找到该字符指向的所有字符，将指向的字符入度-1,表示删除指向的边
        for(auto& nextch : edges[ch]){
            in[nextch]--;
            //如果指向的字符入度减为0，将该字符入队
            if(in[nextch]==0){
                q.push(nextch);
            }
        }
    }

    //遍历入度哈希表，如果出现某个字符的入度不为0，说明顺序错误，不能将所有字符拓扑排序
    for(auto& [ch,count] : in){
        if(count!=0){
            //直接返回空串
            return "";
        }
    }

    //如果拓扑排序完所有字符，说明找到正确顺序，直接返回结果字符串
    return ret;
}

int main(){
    vector<string> tmp = {{"wrt"},
                          {"wrf"},
                          {"er"},
                          {"ett"},
                          {"rftt"}};
   string ret= alienOrder(tmp);
    return 0;
}